package binbaum;
import java.util.Stack;

public class AVLBaum implements IBinBaum{
  protected Knoten hohlkopf;

  public AVLBaum(){
    hohlkopf=new Knoten(Integer.MIN_VALUE);//rlast ohne Bedeutung
  }

  protected Stack<Knoten> pfadZu(int wert){
		Stack<Knoten> pfad=new Stack<Knoten>();
		pfad.clear();
    pfad.push(hohlkopf);
    Knoten lauf=hohlkopf.rson;
    while(lauf!=null && lauf.datum!=wert){
			pfad.push(lauf);
      if(wert<lauf.datum) lauf=lauf.lson;
      else lauf=lauf.rson;
    }
		return pfad;
  }

	@Override
  public boolean contains(int wert){
    Stack<Knoten> pfad=pfadZu(wert);
		Knoten vater=pfad.pop();
    Knoten sohn= wert<vater.datum? vater.lson : vater.rson;
    return sohn!=null && sohn.datum==wert;
  }

	@Override
  public boolean insert(int wert){
    Stack<Knoten> pfad=pfadZu(wert);
		Knoten vater=pfad.pop();
		Knoten sohn=new Knoten(wert);
    if(wert<vater.datum){
      if(vater.lson!=null) return false;
      vater.lson=sohn;
			vater.rlast--;
    } else{
      if(vater.rson!=null) return false;
      vater.rson=sohn;
			vater.rlast++;
    }
		while(Math.abs(vater.rlast)==1 && !pfad.empty()){
			sohn=vater;
			vater=pfad.pop();
			if(sohn==vater.lson) vater.rlast--;
			else vater.rlast++;
    }
		if(vater!=hohlkopf){
			sohn=vater.balanced();
			vater=pfad.pop();
			if(sohn.datum<vater.datum) vater.lson=sohn;
			else vater.rson=sohn;
		}
    return true;
  }

	@Override
  public boolean delete(int wert){
    Stack<Knoten> pfad=pfadZu(wert);
		Knoten v=pfad.peek();
    Knoten s= wert<v.datum? v.lson : v.rson;
    if(s==null) return false;// nichts zu löschen da
    if(s.lson!=null && s.rson!=null){
			v=s;//das datum von v wird nachher überschrieben
			pfad.push(s);
			s=s.rson;// ein Schritt nach rechts...
      while(s.lson!=null){//... dann möglichst nach links
				pfad.push(s);
				s=s.lson;
			}
      v.datum=wert=s.datum;
    }
		v=pfad.pop();
		s= s.lson==null? s.rson : s.lson;
    if(wert<v.datum){//wert==v.datum wird korrekt behandelt
			v.lson=s;
			v.rlast++;
		} else{
			v.rson=s;
			v.rlast--;
		}// ab jetzt wurde genau ein Knoten entfernt
		int vorlast=5;// wir müssen in die Schleife
		while(vorlast!=v.rlast && !pfad.empty()){
			s=v.balanced();
			v=pfad.pop();
			vorlast=v.rlast;
			if(s.datum<v.datum){
				v.lson=s;
			  v.rlast+=1-Math.abs(s.rlast);
			} else{
				v.rson=s;
			  v.rlast-=1-Math.abs(s.rlast);
			}
		}
    return true;
  }

	// Die folgende Inner-Class stellt die nötigen Knoten zur Verfügung.
	//============================================================================
	public static class Knoten implements IBinKnoten{
		public int datum;
		public Knoten lson;//linker  Nachfolger
		public Knoten rson;//rechter Nachfolger
		public int rlast;//um wieviel rechts tiefer als links

		public Knoten(int wert){ datum=wert; }

		public Knoten balanced(){
			if(Math.abs(rlast)<2) return this;
			Knoten sohn= rlast>0? rson:lson;
			if(rlast*sohn.rlast>=0) sohn=rot();
			else sohn=doppelrot();
			return sohn;
		}

		private Knoten doppelrot(){
			if(rlast>0) rson=rson.rot();
			else lson=lson.rot();
			return rot();
		}

		private Knoten rot(){
			Knoten sohn;
			int d;
			if(rlast>0){//Linksrotation
				d=1;
				sohn=rson;
				rson=sohn.lson;
				sohn.lson=this;
			} else{//Rechtsrotation
				d=-1;
				sohn=lson;
				lson=sohn.rson;
				sohn.rson=this;
			}
			rlast=rlast-d-(d*sohn.rlast>0? sohn.rlast:0);
			sohn.rlast=sohn.rlast-d+(d*rlast<0? rlast:0);
			return sohn;
		}

		// Die folgenden Methoden nur für die Zusammenarbeit mit dem Tester.
		@Override
		public IBinKnoten lson(){ return lson; }

		@Override
		public IBinKnoten rson(){ return rson; }

		@Override
		public int datum(){ return datum; }
	}
}